import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;


public class Parser {

	public HashMap<String, Double> s_rules;
	public HashMap<String, Double> t_rules;
	public String[] tags;
	public int tagsCount;
	public String[] words;
	public int wordsCount;
	public double[][][] best;
	public BackP[][][] back;
	public HashMap<String, Integer> tagIndex;
	public HashSet<String> stags;
	public HashSet<String> wordTypes;
	
	class BackP
	{
		int bidx;
		String rule;
	}
	public void prepare()
	{
		for (String s:s_rules.keySet())
			s_rules.put(s, Math.log(s_rules.get(s)));
		for (String s:t_rules.keySet())
			t_rules.put(s, Math.log(t_rules.get(s)));
		tagIndex = new HashMap<String, Integer>();
		for (int i=0; i<tags.length; i++)
			tagIndex.put(tags[i], i);
		stags = new HashSet<String> ();
		for (String s:s_rules.keySet())
		{
			String[] tokens = s.split("\\|");
			//if (tokens[1].indexOf(" ")>=0)
				stags.add(tokens[0]);
		}
	}
	
	public void initialize()
	{
		best = new double[wordsCount+1][wordsCount+1][tagsCount];
		back = new BackP[wordsCount+1][wordsCount+1][tagsCount];
		
		for (int i=0; i<=wordsCount; i++)
		{
			for (int j=0; j<=wordsCount; j++)
			{
				for (int k=0; k<tagsCount; k++)
				{
					best[i][j][k] = Double.NEGATIVE_INFINITY;
					back[i][j][k] = new BackP();
					back[i][j][k].bidx = -1;
					back[i][j][k].rule = null;
				}
			}
		}
		
		for (int i=0; i<wordsCount; i++)
		{
			for (int k=0; k<tagsCount; k++)
			{
				back[i][i+1][k].rule = tags[k]+"|"+words[i];
			}
		}
	}
	public void parse(String mode)
	{
		long start = System.currentTimeMillis();
		// step1
		for (int i=1; i<=wordsCount; i++)
		{
			if (mode.equals("train"))
			{
			for (String s:t_rules.keySet())
			{
				String tokens[] = s.split("\\|");
				if (tokens[1].equals(words[i-1]))
				{
					int tagindex = tagIndex.get(tokens[0]);
					if (best[i-1][i][tagindex] < t_rules.get(s))
					{
						best[i-1][i][tagindex] = t_rules.get(s);
						back[i-1][i][tagindex].bidx = -2;
						back[i-1][i][tagindex].rule = s;
					}
				}
			}
			}
			else
			{
				if (!wordTypes.contains(words[i-1]))
				{
				for (int tagindex=0; tagindex<tagsCount; tagindex++)
				{
					best[i-1][i][tagindex] = 0;
					back[i-1][i][tagindex].bidx = -2;
					back[i-1][i][tagindex].rule = tags[tagindex] + "|" + words[i-1];
				}
				}
				else
				{
					for (String s:t_rules.keySet())
					{
						String tokens[] = s.split("\\|");
						if (tokens[1].equals(words[i-1]))
						{
							int tagindex = tagIndex.get(tokens[0]);
							if (best[i-1][i][tagindex] < t_rules.get(s))
							{
								best[i-1][i][tagindex] = t_rules.get(s);
								back[i-1][i][tagindex].bidx = -2;
								back[i-1][i][tagindex].rule = s;
							}
						}
					}
				}
			}
		}
		
		//step2
		for (int l=2; l<=wordsCount; l++)
		{
			for (int i=0; i<=wordsCount-l; i++)
			{
				int j=i+l;
				for (int k=i+1; k<=j-1; k++)
				{
					for (String s:s_rules.keySet())
					{
						String[] tokens = s.split("\\|");
						if (tokens[1].indexOf(" ")<0)
							continue;
						String[] btags = tokens[1].split(" ");
						//System.out.println(s);
						
						String X=tokens[0];
						String Y=btags[0];
						String Z=btags[1];
						int xindex = tagIndex.get(X);
						int yindex = tagIndex.get(Y);
						int zindex = tagIndex.get(Z);
						double tempp = s_rules.get(s) + best[i][k][yindex] + best[k][j][zindex];
						//if (tempp!=Double.NEGATIVE_INFINITY)
							//System.out.println(tempp);
						if (tempp > best[i][j][xindex])
						{
							if (k==i+1 && k==j-1)
							{
								best[i][j][xindex] = tempp;
								back[i][j][xindex].bidx = k;
								back[i][j][xindex].rule = s;
							}
							else if (k==i+1)
							{
								if (stags.contains(Z))
								{
									best[i][j][xindex] = tempp;
									back[i][j][xindex].bidx = k;
									back[i][j][xindex].rule = s;
								}
							}
							else if (k==j-1)
							{
								if (stags.contains(Y))
								{
									best[i][j][xindex] = tempp;
									back[i][j][xindex].bidx = k;
									back[i][j][xindex].rule = s;
								}
							}
							else
							{
								if (stags.contains(Y)&&stags.contains(Z))
								{
									best[i][j][xindex] = tempp;
									back[i][j][xindex].bidx = k;
									back[i][j][xindex].rule = s;
								}
							}
						}
					}
				}
				boolean again = true;
				int round=0;
				while (again && round<5)
				{
					again=false;
					round++;
					for (String s:s_rules.keySet())
					{
						String[] tokens = s.split("\\|");
						if (tokens[1].indexOf(" ")<0)
						{
							//System.out.println(s);
							double temp = s_rules.get(s) + best[i][j][tagIndex.get(tokens[1])];
							if (temp>=best[i][j][tagIndex.get(tokens[0])])
							{
								//System.out.println("yeah");
								best[i][j][tagIndex.get(tokens[0])] = temp;
								back[i][j][tagIndex.get(tokens[0])].bidx = -3;
								back[i][j][tagIndex.get(tokens[0])].rule = s;
								again=true;
							}
						}
					}
				}
			}
		}
		long end = System.currentTimeMillis();
		long time = end-start;
		//System.out.println("words: " + wordsCount + "time: " + time);
	}
	
	public Node getTree(int i,int j, String X, Node root)
	{
		//System.out.println(i + " " + j);
		//System.out.println(best[i][j][tagIndex.get(X)]);
		/*if (X.equals("TOP") && !(i==0 && j==wordsCount))
		{
			double max = Double.NEGATIVE_INFINITY;
			int maxindex = -1;
			for (int k=0; k<tagsCount; k++)
			{
				if (tags[k].indexOf("TOP")>=0)
				{
					double temp = best[i][j][k];
					if (temp>=max)
					{
						max = temp;
						maxindex=k;
					}
				}
			}
			return getTree(i,j,tags[maxindex],null);
		}*/
		if (root==null)
			root = new Node();
		if (j-i>1)
		{
			//System.out.println(i + " " + j);
			root.value=X;
			//System.out.println(X);
			root.children=new LinkedList<Node>();
			int k=back[i][j][tagIndex.get(X)].bidx;
			//System.out.println(k);
			/*if (k==-1)
				k=i+1;
			System.out.println(back[i][j][tagIndex.get(X)].rule);
			System.out.println(best[i][j][tagIndex.get(X)]);*/
			if (k!=-3)
			{
				//System.out.println();
				String rule;
				/*if (best[i][j][tagIndex.get(X)] == Double.NEGATIVE_INFINITY)
					 rule = "DT NP";
				else*/
					rule = back[i][j][tagIndex.get(X)].rule.split("\\|")[1];
			String Y=rule.split(" ")[0];
			String Z=rule.split(" ")[1];
			Node child1 = new Node();
			child1.parent=root;
			//System.out.println(Y);
			getTree(i,k,Y,child1);
			Node child2 = new Node();
			child2.parent=root;
			getTree(k,j,Z,child2);
			root.children.add(child1);
			root.children.add(child2);
			}
			else
			{
				String Y=back[i][j][tagIndex.get(X)].rule.split("\\|")[1];
				Node child = new Node();
				child.parent = root;
				getTree(i,j,Y,child);
				root.children.add(child);
			}
			return root;
		}
		else
		{
			root.terminal=words[i];
			root.value=X;
			root.children=null;
			return root;
		}
			
	}
	public double logplus(double logx, double logy)
	{
		if (logx==Double.NEGATIVE_INFINITY)
			return logy;
		else if (logy==Double.NEGATIVE_INFINITY)
			return logx;
		else if ((logx-logy) > 32.0)
			return logx;
		else if ((logy-logx) > 32.0)
			return logy;
		else if (logx > logy)
			return logx + Math.log(1.0 + Math.exp(logy - logx));
		else if (logy > logx)
			return logy + Math.log(1.0 + Math.exp(logx - logy));
		else
			return logx + Math.log(2.0);
	}
}

